সার্চিং অ্যালগরিদম (Searching Algorithms)

সার্চিং অ্যালগরিদম হল এমন অ্যালগরিদম যা একটি নির্দিষ্ট ডেটা সেট থেকে একটি নির্দিষ্ট উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয়। সার্চিং অ্যালগরিদমের মধ্যে প্রধানত দুটি সাধারণ শ্রেণি রয়েছে:

1. লিনিয়ার সার্চ (Linear Search): একটি একটি করে উপাদান পরীক্ষা করা হয়।
2. বাইনারি সার্চ (Binary Search): একটি সাজানো (sorted) অ্যারেতে দ্রুত খোঁজার জন্য একটি ইফিসিয়েন্ট অ্যালগরিদম।

এই দুটি অ্যালগরিদমের মধ্যে প্রধান পার্থক্য হল যে লিনিয়ার সার্চ কোন বিশেষ শর্ত ছাড়াই কাজ করে, তবে বাইনারি সার্চ শুধুমাত্র সাজানো অ্যারেতে কাজ করে।

1. লিনিয়ার সার্চ (Linear Search)

লিনিয়ার সার্চ একটি সহজ সার্চিং অ্যালগরিদম যেখানে একটি একটি করে উপাদান যাচাই করা হয় যতক্ষণ না উপাদানটি পাওয়া যায় বা পুরো তালিকাটি পরীক্ষা না করা হয়। এটি একটি O(n) টাইম কমপ্লেক্সিটি প্রদান করে, যেখানে n হলো তালিকার আকার।

লিনিয়ার সার্চের উদাহরণ (Java):

public class LinearSearch {

    // লিনিয়ার সার্চ ফাংশন
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // উপাদান পাওয়া গেলে ইনডেক্স ফেরত দেওয়া হয়
            }
        }
        return -1; // যদি উপাদান না পাওয়া যায়
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50};
        int target = 30;

        int result = linearSearch(arr, target);
        if (result == -1) {
            System.out.println("উপাদানটি পাওয়া যায়নি");
        } else {
            System.out.println("উপাদানটি ইনডেক্স " + result + " তে পাওয়া গেছে");
        }
    }
}

ব্যাখ্যা:

• linearSearch() ফাংশনটি অ্যারের প্রতিটি উপাদান পরীক্ষা করে এবং যদি সেটি টার্গেটের সমান হয়, তাহলে তার ইনডেক্স ফেরত দেয়।
• যদি টার্গেট উপাদানটি না পাওয়া যায়, তবে -1 রিটার্ন করা হয়।

আউটপুট:

উপাদানটি ইনডেক্স 2 তে পাওয়া গেছে

2. বাইনারি সার্চ (Binary Search)

বাইনারি সার্চ একটি ইফিসিয়েন্ট সার্চিং অ্যালগরিদম যা sorted array তে কাজ করে। এটি তালিকার মাঝের উপাদান পরীক্ষা করে এবং তারপর উপাদানটি ডান বা বাম সাইডে অনুসন্ধান করতে শুরু করে। বাইনারি সার্চ O(log n) টাইম কমপ্লেক্সিটি প্রদান করে, যেখানে n হলো অ্যারের আকার। তবে, বাইনারি সার্চ শুধুমাত্র সজ্জিত অ্যারেতে কাজ করে।

বাইনারি সার্চের উদাহরণ (Java):

public class BinarySearch {

    // বাইনারি সার্চ ফাংশন
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // মাঝের উপাদান নির্ধারণ

            if (arr[mid] == target) {
                return mid; // যদি টার্গেট উপাদান পাওয়া যায়
            }
            if (arr[mid] < target) {
                left = mid + 1; // টার্গেট বড় হলে ডান সাইডে অনুসন্ধান
            } else {
                right = mid - 1; // টার্গেট ছোট হলে বাম সাইডে অনুসন্ধান
            }
        }
        return -1; // যদি উপাদান না পাওয়া যায়
    }

    public static void main(String[] args) {
        int[] arr = {10, 20, 30, 40, 50}; // সজ্জিত অ্যারে
        int target = 30;

        int result = binarySearch(arr, target);
        if (result == -1) {
            System.out.println("উপাদানটি পাওয়া যায়নি");
        } else {
            System.out.println("উপাদানটি ইনডেক্স " + result + " তে পাওয়া গেছে");
        }
    }
}

ব্যাখ্যা:

• binarySearch() ফাংশনটি প্রথমে অ্যারের মাঝের উপাদানটি পরীক্ষা করে এবং এরপর টার্গেটের তুলনায় বড় বা ছোট হলে বাম বা ডান সাইডে অনুসন্ধান চালায়।
• O(log n) সময় জটিলতা প্রদান করে কারণ এটি প্রতিটি ধাপে অ্যারের আকারের অর্ধেক কমিয়ে ফেলে।

আউটপুট:

উপাদানটি ইনডেক্স 2 তে পাওয়া গেছে

3. সার্চিং অ্যালগরিদমের তুলনা

4. সার্চিং অ্যালগরিদমের ব্যবহার

1. লিনিয়ার সার্চ:
   • যখন ডেটা অপরিকল্পিত এবং কোনো নির্দিষ্ট সজ্জা নেই, তখন লিনিয়ার সার্চ ব্যবহার করা হয়। উদাহরণস্বরূপ, ছোট ডেটা সেটের মধ্যে দ্রুত অনুসন্ধান।
2. বাইনারি সার্চ:
   • বাইনারি সার্চ একটি সজ্জিত (sorted) ডেটা সেক্টরে দ্রুত ফলাফল পাওয়ার জন্য ব্যবহৃত হয়। এটি বিশাল ডেটাসেটের জন্য অত্যন্ত কার্যকরী। যেমন, বিনারি সার্চ ট্রি, ডাটাবেস ইনডেক্সিং, ডিরেক্টরি সার্চ ইত্যাদিতে।

5. সারাংশ

সার্চিং অ্যালগরিদম আমাদের ডেটা অনুসন্ধানে ব্যবহৃত হয়, যেখানে লিনিয়ার সার্চ সহজ এবং সোজাসুজি প্রক্রিয়া, তবে বাইনারি সার্চ সজ্জিত অ্যারেতে দ্রুত এবং ইফিসিয়েন্ট। Java-তে এই অ্যালগরিদমগুলি O(n) এবং O(log n) টাইম কমপ্লেক্সিটির সঙ্গে কার্যকরীভাবে বাস্তবায়িত করা যায়। বিভিন্ন সমস্যার জন্য সঠিক সার্চিং অ্যালগরিদম নির্বাচন করা গুরুত্বপূর্ণ, যেমন ছোট ডেটাসেটের জন্য লিনিয়ার সার্চ এবং বড় ডেটাসেটের জন্য বাইনারি সার্চ।

Search (অনুসন্ধান) হলো একটি গুরুত্বপূর্ণ অ্যালগরিদম, যা কোনো তালিকা বা অ্যারে থেকে নির্দিষ্ট উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয়। অনুসন্ধান দুই ধরনের হয়ে থাকে: Linear Search এবং Binary Search। এগুলোর মধ্যে পার্থক্য হল যে Linear Search কোন ধরনের সাজানো অ্যারেতে কাজ করতে পারে, যেখানে Binary Search শুধুমাত্র সাজানো অ্যারেতেই কার্যকরী।

Linear Search

Linear Search (লিনিয়ার সার্চ) একটি সাধারণ এবং সহজ পদ্ধতি যা একটি অ্যারে বা তালিকার প্রতিটি উপাদান একে একে পরীক্ষা করে যতক্ষণ না তা নির্দিষ্ট উপাদানটির সাথে মেলে। এটি একটি O(n) অ্যালগরিদম, যেখানে n হল অ্যারের আকার। অর্থাৎ, অ্যারের প্রতিটি উপাদানকে একবার করে পরীক্ষা করতে হয়।

বৈশিষ্ট্য:

• সহজ এবং সরল
• অ্যারে সাজানো কিনা তা কোনো বিষয় নয়
• খারাপ ক্ষেত্রে O(n) সময় জটিলতা

উদাহরণ:

public class LinearSearch {

    // Linear Search function
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // Return the index if found
            }
        }
        return -1; // Return -1 if target is not found
    }

    public static void main(String[] args) {
        int[] arr = {12, 45, 23, 8, 34, 67};
        int target = 23;
        
        int result = linearSearch(arr, target);
        if (result == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

আউটপুট:

Element found at index: 2

এখানে, linearSearch() ফাংশনটি অ্যারের প্রতিটি উপাদান পরীক্ষা করে দেখছে যে কোনো উপাদান target এর সমান কিনা। যদি সমান হয়, তাহলে তার ইনডেক্স রিটার্ন করে, না হলে -1 রিটার্ন করে।

Binary Search

Binary Search (বাইনারি সার্চ) একটি দ্রুত অনুসন্ধান পদ্ধতি যা শুধুমাত্র সাজানো অ্যারেতে কাজ করে। এটি প্রতি ধাপে অ্যারেকে অর্ধেক করে বিভক্ত করে, যেখানে মাঝের উপাদানটি লক্ষ্য উপাদানটির চেয়ে বড় না ছোট তা পরীক্ষা করে। এটি O(log n) সময় জটিলতা প্রদান করে, কারণ প্রতি ধাপে এটি অনুসন্ধান পরিসরকে অর্ধেক করে দেয়।

বৈশিষ্ট্য:

• শুধুমাত্র সাজানো অ্যারেতে কাজ করে
• দ্রুত, কারণ এটি প্রতিটি ধাপে অনুসন্ধান পরিসরকে অর্ধেক করে
• খারাপ ক্ষেত্রে O(log n) সময় জটিলতা

উদাহরণ:

public class BinarySearch {

    // Binary Search function
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;  // To prevent overflow

            // Check if target is present at mid
            if (arr[mid] == target) {
                return mid;
            }

            // If target is smaller, ignore right half
            if (arr[mid] > target) {
                right = mid - 1;
            }
            // If target is larger, ignore left half
            else {
                left = mid + 1;
            }
        }

        return -1;  // Return -1 if target is not found
    }

    public static void main(String[] args) {
        int[] arr = {2, 8, 12, 23, 34, 45, 67};
        int target = 23;
        
        int result = binarySearch(arr, target);
        if (result == -1) {
            System.out.println("Element not found");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

আউটপুট:

Element found at index: 3

এখানে, binarySearch() ফাংশনটি প্রথমে অ্যারের মাঝের উপাদান পরীক্ষা করে, তারপর যদি লক্ষ্য উপাদান তার চেয়ে ছোট হয় তবে ডান দিকে এবং বড় হলে বাম দিকে অনুসন্ধান করতে থাকে। এটি শুধুমাত্র সাজানো অ্যারেতে কাজ করে।

সারাংশ

• Linear Search (লিনিয়ার সার্চ) একটি সহজ এবং সরল পদ্ধতি যা অ্যারের প্রতিটি উপাদানকে একে একে পরীক্ষা করে। এটি সাধারণত ছোট ডেটা সেটে ব্যবহার করা হয় এবং সময় জটিলতা O(n)।
• Binary Search (বাইনারি সার্চ) একটি দ্রুত পদ্ধতি যা শুধুমাত্র সাজানো অ্যারেতে কাজ করে এবং প্রতি ধাপে অনুসন্ধান পরিসরকে অর্ধেক করে দেয়, ফলে সময় জটিলতা O(log n) থাকে।

এই দুটি অ্যালগরিদমের মধ্যে, Binary Search বড় ডেটা সেটে অনেক বেশি কার্যকরী, তবে এটি শুধুমাত্র সাজানো অ্যারেতেই কাজ করে, যেখানে Linear Search যে কোনো অ্যারে বা তালিকার জন্য উপযুক্ত, তবে তা অপেক্ষাকৃত ধীর গতির।

Binary Search Tree (BST)

Binary Search Tree (BST) হলো একটি বিশেষ ধরনের বাইনারি ট্রি যেখানে প্রতিটি নোডের বাঁ পাশের চাইল্ড নোডগুলির মান (value) তার পিতার মানের থেকে ছোট এবং ডান পাশের চাইল্ড নোডগুলির মান তার পিতার মানের থেকে বড় থাকে। এই গুণের কারণে BST একটি স্বতন্ত্র ডাটা স্ট্রাকচার, যা ডেটা খোঁজার, ইনসার্ট এবং ডিলিট অপারেশনগুলোকে দ্রুততর করে তোলে।

BST এর বৈশিষ্ট্য:

1. Left Subtree: একটি নোডের বাম শাখায় থাকা সবগুলো নোড তার পিতার মানের থেকে ছোট।
2. Right Subtree: একটি নোডের ডান শাখায় থাকা সবগুলো নোড তার পিতার মানের থেকে বড়।
3. Unique Values: সাধারণত, BST এ প্রতিটি নোডের একটি ইউনিক মান থাকে।

Binary Search in a BST

Binary Search হল একটি অ্যালগরিদম যা একটি সজ্জিত অ্যারে বা ট্রিতে এলিমেন্ট খুঁজে বের করার জন্য ব্যবহৃত হয়। BST তে, এটি অ্যারে সিকোয়েন্সিংয়ের মতো কাজ করে, যেখানে আপনি ট্রির মধ্যে প্রতি স্টেপে আংশিকভাবে এলিমেন্ট অনুসন্ধান করেন, যতক্ষণ না সঠিক এলিমেন্ট পাওয়া যায়। BST এর এই বৈশিষ্ট্যটি আমাদের সহজেই একটি ভ্যালু খুঁজে পেতে সাহায্য করে।

BST অপারেশন

1. Insertion: BST তে একটি নতুন নোড ইনসার্ট করার জন্য, আপনি সঠিক পজিশনে ইনসার্ট করবেন, যা BST এর গুণাবলী বজায় রাখে।
2. Searching: BST তে একটি নির্দিষ্ট মান খোঁজার জন্য, আপনি প্রতিটি নোডে ভ্যালু চেক করবেন এবং ছোট হলে বাম শাখায়, বড় হলে ডান শাখায় যেতে থাকবেন।

BST এবং Binary Search ইমপ্লিমেন্টেশন

১. BST Node Definition

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

এখানে, Node ক্লাস একটি সাধারণ নোডের জন্য তৈরি করা হয়েছে, যেখানে data হল নোডের মান এবং left, right হলো তার বাম এবং ডান চাইল্ড নোড।

২. BST ইমপ্লিমেন্টেশন

public class BinarySearchTree {
    Node root;

    // Constructor
    public BinarySearchTree() {
        root = null;
    }

    // Insert a new node in the BST
    public void insert(int value) {
        root = insertRec(root, value);
    }

    // Helper function for insertion
    private Node insertRec(Node root, int value) {
        // If the tree is empty, return a new node
        if (root == null) {
            root = new Node(value);
            return root;
        }

        // Otherwise, recur down the tree
        if (value < root.data) {
            root.left = insertRec(root.left, value);
        } else if (value > root.data) {
            root.right = insertRec(root.right, value);
        }

        // return the (unchanged) node pointer
        return root;
    }

    // Search a value in the BST
    public boolean search(int value) {
        return searchRec(root, value);
    }

    // Helper function for searching
    private boolean searchRec(Node root, int value) {
        // Base case: root is null or value is present at the root
        if (root == null) {
            return false;
        }
        if (root.data == value) {
            return true;
        }

        // Value is greater than root's data, search in the right subtree
        if (value > root.data) {
            return searchRec(root.right, value);
        }

        // Value is smaller, search in the left subtree
        return searchRec(root.left, value);
    }

    // In-order traversal of the BST
    public void inorder() {
        inorderRec(root);
    }

    // Helper function for inorder traversal
    private void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }
}

৩. Main Method Example

public class Main {
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // Inserting values into the BST
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        // In-order traversal
        System.out.println("In-order traversal:");
        bst.inorder();  // Output should be sorted: 20 30 40 50 60 70 80
        System.out.println();

        // Searching for a value in the BST
        System.out.println("Search 40: " + bst.search(40));  // true
        System.out.println("Search 100: " + bst.search(100));  // false
    }
}

আউটপুট:

In-order traversal:
20 30 40 50 60 70 80 

Search 40: true
Search 100: false

৪. Binary Search Explanation in BST

BST তে Binary Search ব্যবহার করার সময় আপনি যা করেন তা হলো:

1. প্রথমে মূল নোড (root) থেকে শুরু করবেন।
2. যদি আপনি যে মানটি খুঁজছেন তা মূল নোডের মানের চেয়ে ছোট হয়, তবে আপনি বাম শাখায় চলে যাবেন।
3. যদি মানটি বড় হয়, তবে আপনি ডান শাখায় চলে যাবেন।
4. আপনি এইভাবে যতদিন না আপনি ডেটা খুঁজে পান বা একটি null নোডে পৌছাতে থাকবেন।

এই অ্যালগরিদমটি BST এর কাঠামোকে কাজে লাগিয়ে খুব দ্রুত কাজ করে, যেখানে গড় সময়ে সময় জটিলতা O(log n) হতে পারে, যেখানে n হলো নোডের সংখ্যা।

সারাংশ

Binary Search Tree (BST) একটি বাইনারি ট্রি যেখানে প্রতিটি নোডের বাম শাখায় থাকা মানগুলি তার পিতার চেয়ে ছোট এবং ডান শাখায় থাকা মানগুলি তার পিতার চেয়ে বড় থাকে। এটি Binary Search অপারেশন এর জন্য খুবই কার্যকরী, যেখানে দ্রুত ডেটা খোঁজা সম্ভব হয়। BST এর insert এবং search অপারেশনগুলো গড় সময়ে O(log n) এ সম্পন্ন হয়, যা এটি একটি শক্তিশালী ডাটা স্ট্রাকচার হিসেবে প্রতিষ্ঠিত করে।

এই ইমপ্লিমেন্টেশনটি:

• insert: একটি নতুন নোড ইনসার্ট করা।
• search: একটি নির্দিষ্ট মান খোঁজা।
• inorder traversal: সমস্ত মান সজ্জিত আকারে প্রিন্ট করা।

BST এবং Binary Search সমন্বয়ে একটি খুবই কার্যকরী এবং দক্ষ ডাটা স্ট্রাকচার তৈরী হয় যা স্ট্রিং, নাম্বার বা অন্যান্য অর্ডারড ডেটার জন্য উপযুক্ত।

Searching বা অনুসন্ধান হল একটি ডেটা স্ট্রাকচারের মধ্যে একটি নির্দিষ্ট উপাদান খুঁজে বের করার প্রক্রিয়া। বিভিন্ন ধরনের ডেটা স্ট্রাকচারের জন্য অনুসন্ধান করার সময় time complexity বিভিন্ন হতে পারে। এটি বোঝা গুরুত্বপূর্ণ কারণ এটি প্রভাব ফেলে আপনার প্রোগ্রামের কার্যকারিতা এবং দক্ষতার উপর।

এই টিউটোরিয়ালে আমরা কয়েকটি জনপ্রিয় search algorithms এর time complexity এবং তাদের জাভাতে বাস্তবায়ন দেখব।

১. Search Efficiency এবং Time Complexity

Time complexity হল একটি অ্যালগরিদমের কাজের পরিমাণ, যা ইনপুট সাইজের উপর নির্ভর করে। এটি সাধারণত Big O notation এ প্রকাশ করা হয় এবং বিভিন্ন ধরনের অনুসন্ধান অ্যালগরিদমের সময় জটিলতা ভিন্ন হয়।

প্রধান অনুসন্ধান অ্যালগরিদমগুলো:

1. Linear Search (Sequential Search): একটি অ্যারের প্রতিটি উপাদান একে একে চেক করে নির্দিষ্ট উপাদানটি খোঁজা হয়।
   • Time Complexity: O(n), যেখানে n হল অ্যারের আকার।
2. Binary Search: একটি সাজানো অ্যারে বা তালিকার মধ্যে divide and conquer পদ্ধতি ব্যবহার করে দ্রুত উপাদান খোঁজা হয়।
   • Time Complexity: O(log n), যেখানে n হল অ্যারের আকার।
3. Hash Search: Hashing টেকনিক ব্যবহার করে দ্রুত উপাদান খোঁজা হয়।
   • Time Complexity: O(1) (গড় সময় জটিলতা), যদিও খারাপ কেসে O(n) হতে পারে।
4. Jump Search: একটি সোজা পদ্ধতি যেখানে কিছু ধাপের জন্য উপাদানগুলো পার করে তোলা হয় এবং পরে লিনিয়ারভাবে অনুসন্ধান করা হয়।
   • Time Complexity: O(√n), যেখানে n হল তালিকার আকার।
5. Exponential Search: এটি একটি এলগরিদম যা binary search এর সাথে মিশ্রিত হয় এবং কিছু প্রাথমিক ধাপের জন্য উপাদান খোঁজার কাজ করে।
   • Time Complexity: O(log n)

২. Linear Search (Sequential Search)

Linear Search হল একটি সহজতম অনুসন্ধান অ্যালগরিদম, যেখানে একটি অ্যারের প্রতিটি উপাদান একে একে চেক করা হয় যতক্ষণ না আমাদের কাঙ্ক্ষিত উপাদানটি পাওয়া যায়। এটি সাধারণত সজ্জিত বা অস্বচ্ছ অ্যারে অথবা তালিকার জন্য ব্যবহৃত হয়।

উদাহরণ: Linear Search in Java

public class LinearSearchExample {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;  // Found the target, return its index
            }
        }
        return -1;  // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 9, 1, 6};
        int target = 9;
        int result = linearSearch(arr, target);
        
        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found.");
        }
    }
}

ব্যাখ্যা:

• Time Complexity: O(n) - এখানে n হল অ্যারের আকার, কারণ সব উপাদান পরীক্ষা করতে হতে পারে।

আউটপুট:

Element found at index: 2

৩. Binary Search

Binary Search হল একটি দ্রুত অনুসন্ধান অ্যালগরিদম যা শুধুমাত্র সজ্জিত অ্যারে বা তালিকার জন্য ব্যবহারযোগ্য। এটি divide and conquer পদ্ধতি ব্যবহার করে যেখানে প্রতিটি ধাপে অ্যারের মাঝখানে গিয়ে এলিমেন্টটির অবস্থান খোঁজা হয়।

উদাহরণ: Binary Search in Java

public class BinarySearchExample {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;  // Calculate the mid index

            // Check if target is present at mid
            if (arr[mid] == target) {
                return mid;
            }

            // If target is greater, ignore left half
            if (arr[mid] < target) {
                left = mid + 1;
            } 
            // If target is smaller, ignore right half
            else {
                right = mid - 1;
            }
        }

        return -1;  // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 6, 9};
        int target = 6;
        int result = binarySearch(arr, target);

        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found.");
        }
    }
}

ব্যাখ্যা:

• Time Complexity: O(log n) - অ্যারে প্রতিটি ধাপে অর্ধেক ভাগ হয়ে যায়, এবং শুধুমাত্র সাজানো অ্যারের জন্য এটি কার্যকর।

আউটপুট:

Element found at index: 3

৪. Hash Search (HashMap)

Hashing একটি পদ্ধতি যা কীগুলির জন্য একটি হ্যাশ ফাংশন ব্যবহার করে দ্রুত অনুসন্ধান এবং অ্যাক্সেস করতে সাহায্য করে। HashMap একটি জনপ্রিয় ডেটা স্ট্রাকচার যা key-value pairs ধরে রাখে এবং এর মাধ্যমে খুব দ্রুত অনুসন্ধান সম্ভব হয়।

উদাহরণ: HashMap Search in Java

import java.util.HashMap;

public class HashSearchExample {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("Apple", 5);
        map.put("Banana", 3);
        map.put("Cherry", 7);

        String target = "Banana";
        if (map.containsKey(target)) {
            System.out.println(target + " found with value: " + map.get(target));
        } else {
            System.out.println(target + " not found.");
        }
    }
}

ব্যাখ্যা:

• Time Complexity: O(1) গড় সময়ে (hashing এর কারণে), তবে খারাপ কেসে (যদি হ্যাশ কলিশন ঘটে) O(n) হতে পারে।

আউটপুট:

Banana found with value: 3

৫. Jump Search

Jump Search একটি অনুসন্ধান অ্যালগরিদম যা একটি সজ্জিত অ্যারের মধ্যে ধাপে ধাপে অনুসন্ধান করে। এটি কিছু উপাদান পাড়ি দিয়ে খোঁজ শুরু করে, তারপর লিনিয়ারভাবে আগের ধাপে ফিরে আসতে থাকে।

উদাহরণ: Jump Search in Java

public class JumpSearchExample {
    public static int jumpSearch(int[] arr, int target) {
        int n = arr.length;
        int step = (int) Math.sqrt(n);  // Jump size
        int prev = 0;

        // Jump to the next block
        while (arr[Math.min(step, n) - 1] < target) {
            prev = step;
            step += (int) Math.sqrt(n);
            if (prev >= n) {
                return -1; // Target not found
            }
        }

        // Perform linear search within the block
        for (int i = prev; i < Math.min(step, n); i++) {
            if (arr[i] == target) {
                return i;
            }
        }

        return -1;  // Target not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 6, 9};
        int target = 6;
        int result = jumpSearch(arr, target);

        if (result != -1) {
            System.out.println("Element found at index: " + result);
        } else {
            System.out.println("Element not found.");
        }
    }
}

ব্যাখ্যা:

• Time Complexity: O(√n) - প্রতিটি ধাপে অর্ধেক সাইজের ব্লক পাড়ি দেওয়া হয়, তারপর লিনিয়ারভাবে চেক করা হয়।

আউটপুট:

Element found at index: 3

৬. Time Complexity Summary of Searching Algorithms

সারাংশ

Searching Algorithms হল ডেটার মধ্যে দ্রুত নির্দিষ্ট উপাদান খুঁজে বের করার জন্য ব্যবহৃত টেকনিক। Linear Search, Binary Search, Hash Search, এবং Jump Search এর মতো বিভিন্ন অ্যালগরিদমের বিভিন্ন time complexity এবং space complexity রয়েছে। আপনার প্রয়োজনে সঠিক অনুসন্ধান অ্যালগরিদম নির্বাচন করে, আপনি কোডের কার্যকারিতা অনেক বেশি উন্নত করতে পারবেন।

Searching Algorithms ডেটা স্ট্রাকচারের মধ্যে নির্দিষ্ট একটি উপাদান খোঁজার জন্য ব্যবহৃত হয়। Linear Search এবং Binary Search হল সাধারণত ব্যবহৃত দুটি অনুসন্ধান পদ্ধতি, তবে কিছু উন্নত অনুসন্ধান পদ্ধতিও রয়েছে, যেমন Jump Search, Interpolation Search, এবং Exponential Search। এই অ্যালগরিদমগুলি অনেক সময় বিশেষ ক্ষেত্রে অধিক কার্যকরী হতে পারে, যেমন সেগুলির ইনপুট ডেটা পূর্বে সাজানো থাকে বা নির্দিষ্ট ধরণের প্রোপার্টি থাকে।

এই টিউটোরিয়ালে, আমরা Jump Search, Interpolation Search, এবং Exponential Search অ্যালগরিদমগুলোর কার্যপ্রণালী এবং Java তে তাদের বাস্তবায়ন আলোচনা করব।

1. Jump Search

Jump Search হল একটি অনুসন্ধান অ্যালগরিদম যা একটি সাজানো অ্যারের মধ্যে দ্রুত অনুসন্ধান করার জন্য ব্যবহৃত হয়। এটি Block Search পদ্ধতির ওপর ভিত্তি করে কাজ করে, যেখানে অ্যারের মধ্যে একটি নির্দিষ্ট সাইজের "ঝাঁপ" (block) তৈরি করা হয়, তারপর ধীরে ধীরে এগিয়ে গিয়ে উপাদানটি খোঁজা হয়।

Steps:

1. অ্যারের মধ্যে একটি বর্গমূল আকৃতির ব্লক নির্বাচন করা হয়।
2. ব্লক ব্লক করে এগিয়ে যায় এবং একটি উপাদান পাওয়া গেলে, সেটি ডিটেইলসভাবে খোঁজা হয়।

উদাহরণ: Jump Search

public class JumpSearch {
    public static int jumpSearch(int[] arr, int key) {
        int n = arr.length;
        int step = (int) Math.sqrt(n);  // Calculate block size (step)

        int prev = 0;
        while (arr[Math.min(step, n) - 1] < key) {
            prev = step;
            step += (int) Math.sqrt(n);
            if (prev >= n) {
                return -1;  // Key not found
            }
        }

        // Linear search for key in block defined by prev and step
        for (int i = prev; i < Math.min(step, n); i++) {
            if (arr[i] == key) {
                return i;
            }
        }

        return -1;  // Key not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21};
        int key = 15;
        int index = jumpSearch(arr, key);
        if (index != -1) {
            System.out.println("Element found at index: " + index);
        } else {
            System.out.println("Element not found");
        }
    }
}

ব্যাখ্যা:

1. step: ব্লকের আকারটি sqrt(n) হিসাবে নির্ধারণ করা হয়।
2. অ্যারের মধ্যে ধীরে ধীরে ব্লক অনুসন্ধান করা হয়, এরপর নির্দিষ্ট ব্লকে linear search ব্যবহার করে উপাদানটি খোঁজা হয়।

আউটপুট:

Element found at index: 7

2. Interpolation Search

Interpolation Search হল একটি উন্নত অনুসন্ধান অ্যালগরিদম যা সোজা অঙ্কন বা ইনপুট ডেটার মানের উপর ভিত্তি করে অ্যারের মধ্যে একটি উপাদান খোঁজে। এটি Binary Search এর মতো, তবে এটি পুরো অ্যারের মধ্য থেকে সম্ভাব্য অবস্থান নির্ধারণ করে এবং সঠিক অবস্থানে পৌঁছানোর জন্য এটি ইনপুট ডেটা মানের ওপর ভিত্তি করে অনুসন্ধান করে।

Steps:

1. প্রথমে দুইটি সূচক (low এবং high) ব্যবহার করে, সেগুলির মধ্যে পরবর্তী সম্ভাব্য অবস্থান অনুমান করা হয়।
2. এটি পরবর্তী অবস্থান থেকে অনুসন্ধান শুরু করে।

উদাহরণ: Interpolation Search

public class InterpolationSearch {
    public static int interpolationSearch(int[] arr, int key) {
        int low = 0, high = arr.length - 1;

        while (low <= high && key >= arr[low] && key <= arr[high]) {
            int pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low]);
            
            // Check if key is found at pos
            if (arr[pos] == key) {
                return pos;
            }
            
            if (arr[pos] < key) {
                low = pos + 1;
            } else {
                high = pos - 1;
            }
        }

        return -1;  // Key not found
    }

    public static void main(String[] args) {
        int[] arr = {10, 12, 18, 20, 35, 40, 45, 50, 55, 60};
        int key = 35;
        int index = interpolationSearch(arr, key);
        if (index != -1) {
            System.out.println("Element found at index: " + index);
        } else {
            System.out.println("Element not found");
        }
    }
}

ব্যাখ্যা:

1. Interpolation Formula: pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low])
   • এটি সম্ভাব্য অবস্থান গণনা করে।
2. যদি key সরাসরি পাওয়া না যায়, তবে low এবং high সূচকগুলিকে সংশোধন করা হয়।

আউটপুট:

Element found at index: 4

3. Exponential Search

Exponential Search হল একটি অনুসন্ধান অ্যালগরিদম যা প্রথমে একটি বৃহত্তম পাওয়া এলিমেন্ট খোঁজার জন্য একটি এক্সপোনেনশিয়াল স্টেপের মাধ্যমে অ্যারের মধ্যে সরে যায় এবং পরে Binary Search ব্যবহার করে যথাযথ অবস্থান অনুসন্ধান করে।

Steps:

1. প্রথমে এক্সপোনেনশিয়ালভাবে অবস্থান বাড়ানো হয়।
2. একবারে যেটি পৌঁছানো হয়, সেখানে Binary Search ব্যবহার করা হয়।

উদাহরণ: Exponential Search

public class ExponentialSearch {
    public static int exponentialSearch(int[] arr, int key) {
        int n = arr.length;
        if (arr[0] == key) {
            return 0;  // If the element is at index 0
        }

        int i = 1;
        while (i < n && arr[i] <= key) {
            i = i * 2;  // Exponentially increase the index
        }

        return binarySearch(arr, key, i / 2, Math.min(i, n - 1)); // Perform binary search
    }

    private static int binarySearch(int[] arr, int key, int low, int high) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == key) {
                return mid;
            } else if (arr[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;  // Key not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
        int key = 15;
        int index = exponentialSearch(arr, key);
        if (index != -1) {
            System.out.println("Element found at index: " + index);
        } else {
            System.out.println("Element not found");
        }
    }
}

ব্যাখ্যা:

1. Exponential Search: প্রথমে এক্সপোনেনশিয়ালভাবে i বাড়ানো হয়, যতক্ষণ না উপাদানটি পাওয়া যায় বা খুঁজে বের করা হয়।
2. একবার উপযুক্ত Binary Search সীমা চিহ্নিত হলে, সেখানেই Binary Search চালানো হয়।

আউটপুট:

Element found at index: 7

সারাংশ

এই তিনটি উন্নত অনুসন্ধান অ্যালগরিদম হল:

1. Jump Search: এটি একটি সাজানো অ্যারের মধ্যে ব্লক ভিত্তিক অনুসন্ধান পদ্ধতি যা ব্লক ব্লক করে কাজ করে।
2. Interpolation Search: এটি একটি উন্নত Binary Search যা ইনপুট ডেটার মানের উপর ভিত্তি করে অনুসন্ধান করে।
3. Exponential Search: এটি এক্সপোনেনশিয়ালভাবে অবস্থান বাড়িয়ে পরে Binary Search ব্যবহার করে দ্রুত অনুসন্ধান করে।

এই অ্যালগরিদমগুলির মাধ্যমে একটি সাজানো অ্যারে থেকে উপাদান দ্রুত খুঁজে পাওয়া সম্ভব, বিশেষ করে যখন ডেটা নির্দিষ্ট প্যাটার্নে সাজানো থাকে।